import java.util.PrimitiveIterator;

public class MySort {
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++){
            int tmp = array[i] ;
            int j = i -1 ;
            for (; j >= 0 ; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{

                    break ;
                }
            }
            array[j+1] = tmp ;
        }

    }
    public static void shellSort(int[] array){
        int gap = array.length  ;
         while(gap > 1){
             gap = gap/2 ;
             shell(array , gap);
         }
    }
    private static void shell(int[] array , int gap){
        for (int i = gap; i < array.length ; i++) {
            int tmp = array[i] ;
            int j = i-gap ;
            for (; j >= 0 ; j -= gap) {
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break ;
                }
            }
              array[j+gap] = tmp;
        }

    }
    private static void swap(int[] array , int i , int j){
        int tmp = array[i] ;
        array[i] = array[j] ;
        array[j] = tmp ;
    }
    public static void selectSort1(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
         int minIndex = left ;
         int maxIndex = left ;
            for (int i = left+1; i <= right ; i++) {
                if(array[i] > array[maxIndex]){
                    maxIndex = i ;
                }
                if(array[i] < array[minIndex]){
                    minIndex = i ;
                }
            }
            swap(array , left , minIndex);
            if(maxIndex == left){
                swap(array , right , minIndex);
            }else{
                swap(array , right , maxIndex);
            }
            left ++ ;
            right -- ;
        }


    }
    public static void heapSort(int[] array){
           createHeap(array);
    }
    private static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2 ; parent >= 0 ; parent--) {
            shiftDown(array , parent , array.length);
        }
        for (int i = array.length-1; i > 0 ; i--) {
            swap(array , 0 , i);
            shiftDown(array , 0 , i);
        }

    }
    private static void shiftDown(int[] array , int parent , int len){
        int child = parent*2 + 1 ;
        while(child < len){
            if(child+1 < len && array[child] < array[child+1]){
                child ++ ;
            }
            if(array[parent] < array[child]){
                swap(array, parent , child);
                parent = child ;
                child = parent*2 +1 ;
            }else{
                break ;
            }
        }

    }


public static void quickSort(int[] array){
      quick(array , 0 , array.length-1);
}
private static int partitionHoare(int[] array , int left , int right){
        int key = array[left] ;
        int tmp = left ;
        while(left < right){
            while (left < right && key <= array[right]){
                right -- ;
            }
            while (left < right && key >= array[left]){
                left ++ ;
            }
            swap(array , left , right);
        }
        swap(array , tmp , left);
        return left ;
}
private static void quick(int[] array , int start , int end){
   if(start >= end) return ;
    int pivot = partitionHoare(array , start , end);
    quick(array , start , pivot-1);
    quick(array , pivot+1 , end);
}
public static void wk(int[] array){
        wk2(array , 0 , array.length -1);
}
private static void wk2(int[] array , int start , int end){
        if(start >= end) return ;
        int pivot = partition(array , start , end);
        wk2(array , start , pivot-1);
        wk2(array , pivot+1 , end) ;
}
private static int partition(int[] array , int left , int right){
        int key = array[left];
        while(left < right){
            while(left < right && array[right] >= key){
                right -- ;
            }
            array[left] = array[right];
            while (left < right && array[left] <= key){
                left ++ ;
            }
            array[right] = array[left] ;
        }
          array[left] = key ;
             return left ;
}





}



























